package leetcode.dynamic;

/**
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "rabbbit", t = "rabbit"
 * 输出：3
 * 解释：
 * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
 * rabbbit
 * rabbbit
 * rabbbit
 * 示例 2：
 * <p>
 * 输入：s = "babgbag", t = "bag"
 * 输出：5
 * 解释：
 * 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 */
public class LeetCode115_NumDistinct {
    public int numDistinct(String s, String t) {
        return f(s.toCharArray(), t.toCharArray(), s.length() - 1, t.length() - 1);
    }

    public int f(char[] s1, char[] s2, int i, int j) {
        if (j < 0) {
            return 1;
        }
        if (i < 0) {
            return 0;
        }

        int ans = 0;
        if (s1[i] == s2[j]) {
            ans = f(s1, s2, i - 1, j - 1);
        }
        return ans + f(s1, s2, i - 1, j);
    }

    public int numDistinct2(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] s2 = t.toCharArray();
        int[][] dp = new int[s1.length][s2.length];

        dp[0][0] = (s1[0] == s2[0] ? 1 : 0);
//        for (int i = 1; i < s1.length; i++) {
//            dp[0][i] = dp[0][i - 1] + (s2[i] == s1[0] ? 1 : 0);
//        }
        for (int i = 1; i < s1.length; i++) {
            dp[i][0] = dp[i - 1][0] + (s2[0] == s1[i] ? 1 : 0);
        }

        for (int i = 1; i < s1.length; i++) {
            for (int j = 1; j < s2.length; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }

        return dp[s1.length - 1][s2.length - 1];
    }

}
